{ "cells": [ { "cell_type": "markdown", "source": [ "# Mathematical Nirvana\n", "## Problem Definition\n", "Nathaniel Richards is a young, brilliant scientist that has developed the following Non-Linear Programming (NLP) problem to find the optimal balance between studying and meditating to maximize the overall satisfaction and achieve a state of enlightenment (Mathematical Nirvana).\n", "\n", "**Decision Variables:**\n", "Let:\n", "\n", "$x_1$ Time spent studying (in hours)\n", "\n", "$x_2$ = Time spent meditating (in hours)\n", "\n", "$x = [x_1, x_2]$ The set of decision variables\n", "\n", "$x_1, x_2 \\geq 0$\n", "\n", "**Objective Function:**\n", "Maximize the overall satisfaction obtained from studying and meditating:\n", "\n", "$\\max z = f(x) = 2*x_1+0.5*\\ln(1+x_1) + 0.7*x_2 + 0.3*\\sqrt(x_2)$\n", "\n", "**Constraints:**\n", "Subject to:\n", "Maximum amount of time available:\n", "\n", "$x_1 + x_2 \\leq 10$\n", "\n", "Minimum amount of time studying to ensure academic performance:\n", "\n", "$x_1 \\geq 2$\n", "\n", "Unfortunately Nathaniel mysteriously disappeared before he could completely analyse the problem, so you need to complete his work according to the following instructions:\n", "\n" ], "metadata": { "collapsed": false } }, { "cell_type": "markdown", "source": [ "1. Obtain the Kuhn-Tucker conditions\n", "To obtain the Kuhn-Tucker conditions, let us first get the Lagrangian function:\n", "\n", "$L(x,\\lambda) = f(x) + \\lambda_1(g_1(x)) - \\lambda_2(g_2(x))$\n", "\n", "$L(x,\\lambda) = 2*x_1+0.5*\\ln(1+x_1) + 0.7*x_2 + 0.3*\\sqrt(x_2) + \\lambda_1(x_1 + x_2 - 10) + \\lambda_2(-x_1 + 2)$\n", "\n", "Note that to obtain the expression above we have first express the problem in a canonical form where all the constraints are inequalities of type $\\leq$.\n", "\n", "Now, we can obtain the Kuhn-Tucker conditions by taking the partial derivatives of the Lagrangian function with respect to the decision variables and the Lagrangian multipliers:\n", "\n", "- **Gradient Conditions:** $\\nabla_x L(x,\\lambda) = 0$\n", "\n", "$\\Large \\frac{\\partial L}{\\partial x_1} = 2 + \\frac{0.5}{1+x_1} + \\lambda_1 - \\lambda_2 = 0$\n", "\n", "$\\Large \\frac{\\partial L}{\\partial x_2} = 0.7 + \\frac{0.3}{2\\sqrt{x_2}} + \\lambda_1 = 0$\n", "\n", "- **Orthogonality Conditions:** $\\lambda_i g_i(x) = 0$\n", "\n", "$\\Large \\lambda_1(x_1 + x_2 - 10) = 0$\n", "\n", "$\\Large \\lambda_2(-x_1 + 2) = 0$\n", "\n", "- **Feasibility Conditions:** $g_i(x) \\leq 0$\n", "\n", "$x_1 + x_2 - 10 \\leq 0$\n", "\n", "$-x_1 + 2 \\leq 0$\n", "\n", "- **Non-negativity Conditions:**\n", "\n", "$\\lambda_1, \\lambda_2 \\leq 0$\n", "$x_1, x_2 \\geq 0$\n" ], "metadata": { "collapsed": false } }, { "cell_type": "markdown", "source": [ "\n", "2. Obtain the Hessian and determine if this solution ($x_1 = 3.9, x_2 = 6.1$) is a global or local maximum\n", "To obtain the Hessian matrix, we need to take the second derivatives of the objective function with respect to the decision variables:\n", "\n", "$\\Large \\frac{\\partial^2 f(x)}{\\partial x_1^2} = -\\frac{0.5}{(1+x_1)^2} \\leq 0$\n", "\n", "$\\Large \\frac{\\partial^2 f(x)}{\\partial x_2^2} = -\\frac{0.3}{4*x_2^{3/2}} \\leq 0$\n", "\n", "$\\Large \\frac{\\partial^2 f(x)}{\\partial x_1 \\partial x_2} = 0$\n", "\n", "$\\Large \\frac{\\partial^2 f(x)}{\\partial x_2 \\partial x_1} = 0$\n", "\n", "Now, we can obtain the Hessian matrix:\n", "\n", "$\\Large H(x) = \\begin{bmatrix}\n", "-\\frac{0.5}{(1+x_1)^2} & 0 \\\\\n", "0 & -\\frac{0.3}{4*x_2^{3/2}}\n", "\\end{bmatrix}$\n", "\n", "To determine if the solution is a global or local maximum, we need to check the definiteness of the Hessian matrix for the values $x_1 = 3.9, x_2 = 6.1$:\n", "\n", "$\\Large H(x) = \\begin{bmatrix}\n", "-\\frac{0.5}{(1+3.9)^2} & 0 \\\\\n", "0 & -\\frac{0.3}{4*6.1^{3/2}}\n", "\\end{bmatrix} = \\begin{bmatrix}\n", "-0.02 & 0 \\\\\n", "0 & -0.005\n", "\\end{bmatrix}$\n", "\n", "The first determinant is negative ($h_1 = -0.02$), and the second determinant is positive ($h_2 = -0.02*-0.005 > 0$), so the Hessian matrix is indefinite. Therefore, the test is inconclusive.\n", "If we look at the Hessian matrix of the equivalent minimization problem ($\\min f*(x) = -f(x)$), since now the Hessian becomes:\n", "\n", "$H(x) =\\begin{bmatrix}\n", "0.02 & 0 \\\\\n", "0 & 0.005\n", "\\end{bmatrix}$\n", "\n", "we can see that it is positive definite ($h_1 = 0.02, h_2 = 0.02*0.005 > 0$), so the solution is a global minimum, and therefore the solution to the original maximization problem is a global maximum.\n", "\n", "5. Use the Kuhn-Tucker conditions to calculate the Lagrangian multipliers for this solution, can you explain what they mean? Discuss if this can be an optimal solution to the problem\n", "\n", "Now, we can use the Kuhn-Tucker conditions to calculate the Lagrangian multipliers for this solution. From the gradient conditions, we have:\n", "\n", "$\\Large \\frac{\\partial L}{\\partial x_1} = 2 + \\frac{0.5}{1+3.9} + \\lambda_1 - \\lambda_2 = 0$\n", "\n", "$\\Large \\frac{\\partial L}{\\partial x_2} = 0.7 + \\frac{0.3}{2\\sqrt{6.1}} + \\lambda_1 = 0$\n", "\n", "From the second gradient condition, we can obtain the value of $\\lambda_1$:\n", "\n", "$\\Large \\lambda_1 = -0.7 - \\frac{0.3}{2\\sqrt{6.1}} = -0.8$\n", "\n", "From the first gradient condition, we can obtain the value of $\\lambda_2$:\n", "\n", "$\\Large \\lambda_2 = 2 + \\frac{0.5}{1+3.9} + \\lambda_1 = 1.35$\n", "\n", "The Lagrangian multipliers obtained do not satisfy the orthogonality conditions and non-negative conditions, so this solution cannot be optimal.\n", "\n" ], "metadata": { "collapsed": false } } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.6" } }, "nbformat": 4, "nbformat_minor": 0 }